/*
 * @Author: YiY
 * @Date: 2024-01-08 09:04:11
 * @LastEditTime: 2024-01-09 10:41:33
 */

function mergeSort(arr) {
  let list = JSON.parse(JSON.stringify(arr))
  let len = arr.length;

  let lList = []
  let rList = []
  let result = []

  if (len == 1) {
    result.push(list[0])
  } else if (len == 2) {
    list[0] > list[1] ? rList.push(list[0]) : lList.push(list[0])
    list[1] > list[0] ? rList.push(list[1]) : lList.push(list[1])
    result = lList.concat(rList)

  } else if (len > 2) {
    let mid = Math.floor(len / 2)
    let lList = list.slice(0, mid)
    let rList = list.slice(mid)
    lList = mergeSort(lList)
    rList = mergeSort(rList)

    let l = 0
    let r = 0

    while ((l + r) != len) {
      if (l == lList.length) {
        result.push(rList[r++])
        continue
      }
      if (r == rList.length) {
        result.push(lList[l++])
        continue
      }
      lList[l] < rList[r] ? result.push(lList[l++]) : result.push(rList[r++])

      console.log(`l:${lList[l]}+++r:${rList[r]}`)
    }
    return result
  }

  console.log('result :>> ', result);
  return result
}

// 测试数据
let arr = [9, 8, 7, 6, 5, 4, 3, 2, 1];
console.log("原始数组：", arr);
console.log("归并排序后：", mergeSort(arr));
